# coding: utf-8

# 作者：雪山凌狐
# 题目：
# 有两个空杯子，容量不同，还有一个水池可以接水。
# 给定一个需要的水的容量，如何通过已有的两个杯子倒腾出所需的水的容量？

'''
首先我们来举一下实际的数据方便理解。
比如有两个杯子，杯子1 可以装的水为 4ml，杯子2 可以装的水为 9ml。
现在比如我需要拿到 6ml 的水请问如何实现？（没有其他工具辅助）
如果需要拿 7ml 的水呢？

这是一个步骤规划的问题，类似坐标轴上走每个点，直到走到合适的点位
'''

def situations(x, y, X, Y):
    """
    返回一个字典，水杯变化的各种情况。
    假定两个水杯原有的水量分别为 x（我们叫杯a），y（我们叫杯b）
    而两个水杯装满水的水量为 X（我们叫杯a），Y（我们叫杯b）
    就是本函数的四个参数
    """
    return {
        # 我们枚举抽象总结出下面六种情况：
        # 前面四种都比较好理解  
        (X, y): '灌满X',
        (x, Y): '灌满Y',
        (0, y): '倒空X',
        (x, 0): '倒空Y',
        # 下面两种键的形式有一个很大的特点那就是键是有条件计算的！！
        # X 倒给 Y 的时候，需要考虑是否太满的问题
        # 如果原有的水量加起来没有达到 杯b 的最大水量，则为 (0, x + y)
        # 如果水量超过，则 杯a 的最新水量为 x + y - Y，杯b 装满所以为 Y
        ((0, y + x) if x + y <= Y else (x + y - Y, Y)): 'X 倒给 Y',
        # 同理 Y 倒给 X 的时候，也要考虑一样的问题
        ((x + y, 0) if x + y <= X else (X, x + y - X)): 'Y 倒给 X'
    }

def water_pouring(b1, b2, goal, start=(0, 0)):
    """
    倒水规划函数
    b1：杯子a的总容量
    b2：杯子b的总容量
    goal：目标需要的容量
    start：初始的时候两个杯子的容量，分别为杯a、杯b，元组形式表示
    """
    
    # 如果初始的时候的两杯数量中含有目标水量，那结果就已经出来了，不用搞了
    if goal in start: 
        return [start]

    # 曾经用过的方法方式，走过的路子，就不会重复走了，所以用集合来存储
    explored = set()
    # 起始状态
    steps = [[('起始状态', start)]]

    while steps:
        # 每一个 path 保存着一条尝试的路线，取一条路线出来测试能否满足
        path = steps.pop()
        # 路线中先取最后一步的动作和位置，然后再取位置坐标，赋值给 x，y
        (x, y) = path[-1][-1]
        
        # 对下一步可能的路线进行循环探测，可能的路线通过 situations 函数返回所有可能路线
        for (state, action) in situations(x, y, b1, b2).items():
            # 如果该路线没探索过，加入已探索列表中（不允许重复探索，因为是 set）
            if state not in explored:
                explored.add(state)

                # 最新的路线图加上刚探索的那一步进来
                path2 = path + [(action, state)]

                # 如果已经实现目标，直接返回路线图
                if goal in state:
                    return path2
                # 如果还未实现目标，则把最新路线图加到总图的最前方
                # 因为前面 pop() 路线的时候取的是最后一个，所以这里将最新路线插入到第一个
                # 你也可以前面用 pop(0) 取第一个，这里 append 到最后一个
                else:
                    steps.insert(0, path2)

    # 如果 steps 中的所有路线图均已探索完成都没有结果，那么说明无法满足要求，返回空路线图
    return []

def show_results(path):
    """用来美观的展示路线图的"""
    for i in path:
        print(i[0] + " --> " + str(i[1]))
    print()

if __name__ == '__main__':
    print("获取 5ml 的水：")
    show_results(water_pouring(4, 9, 5))
    print("获取 6ml 的水：")
    show_results(water_pouring(4, 9, 6, start=(4, 9)))
    print("获取 7ml 的水：")
    show_results(water_pouring(4, 9, 7, start=(4, 0)))